class Solution:
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        dp = [False] * (len(s)+1)
        dp[0] = True
        map = {}
        for i in wordDict:
            map[i] = True
        for i in range(1, len(s)+1):
            for j in range(0, i):
                if dp[j] is True and s[j:i] in map:
                    dp[i] = True
                    break
        return dp[len(s)]

